package LeetCode._03_链表;

public class _03环形链表2 {
    class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    public ListNode detectCycle(ListNode head) {
        if(head == null) return null;
        ListNode slow = head,fast = head;
        while(fast!=null && fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast) break; //相遇或者走到了链表尾部
        }

        if(fast == null || fast.next == null) return null; //无循环的情况

        //有环的情况下，从相遇点到入环口的距离 == 头节点到入环口的距离
        fast = head;
        while(fast!=slow){
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }
}
